package medium;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/10/29 20:01
 */
public class No47_全排列II {
    public static void main(String[] args) {
        Solution47 solution47 = new Solution47();
        int[] nums = new int[]{1,2,3,3};
        List<List<Integer>> lists = solution47.permuteUnique(nums);
        System.out.println(lists);

    }
}

class Solution47 {
    
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        
        //map初始化
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            addMapKeys(map, num);
        }
        List<Integer> data = new ArrayList<>();
        permuteUnique(nums, map, data);
        return res;
    }

    //map:哈希映射
    //data:递归数
    public void permuteUnique(int[] nums, Map<Integer, Integer> map, List<Integer> data) {
        if (data.size() == nums.length) {
            //值传递
            List<Integer> dataCopy = new ArrayList<>(data);
            res.add(dataCopy);
            return;
        }
        
        //遍历map:通过map处理第一轮递归了a又递归了第二个a这种重复问题
        for (Map.Entry<Integer, Integer> mapData : map.entrySet()) {
            //如果递归元素<=0不可递归
            //元素
            Integer key = mapData.getKey();
            //个数
            Integer value = mapData.getValue();
            if (value > 0) {
                //才可以递归
                //key个数-1
                map.put(key, value - 1);
                data.add(key);
                permuteUnique(nums,map,data);
                //回溯联动
                data.remove(data.size() - 1);
                //个数+回去
                map.put(key, value);
            }
        }
    }


    public void addMapKeys(Map<Integer, Integer> map, int key) {
        if (map.get(key) == null) {
            map.put(key, 1);
        } else {
            map.put(key, map.get(key) + 1);
        } 
    }
}



    //public List<List<Integer>> permuteUnique(int[] nums) {
    //    // 221:  122,212
    //    //暴力法
    //    List<Integer> data = new ArrayList<>();
    //    permuteUnique(nums,data);
    //    return res;
    //}
    //
    ////已递归索引
    //Set<Integer> overIndexs = new HashSet<>();
    ////全排列重复检查
    //Set<String> check = new HashSet<>();
    //List<List<Integer>> res = new ArrayList<>();
    //public void permuteUnique(int[] nums, List<Integer> data) {
    //
    //    if (overIndexs.size() == nums.length) {
    //        //值传递
    //        List<Integer> dataCopy = new ArrayList<>(data);
    //        //注意2aldsfjla2aldsfjla13跟2aldsfjla2aldsfjla13的区别
    //        String base = "";
    //        for (int d : dataCopy) {
    //            base += d + "aldsfjla";
    //        }
    //        if (check.add(base)) {
    //            res.add(dataCopy);
    //        }
    //        return;
    //    }
    //    
    //    
    //    
    //    for (int i = 0; i < nums.length; i++) {
    //        if (overIndexs.add(i)) {
    //            //已递归数
    //            int add = nums[i];
    //            data.add(add);
    //            permuteUnique(nums, data);
    //            //回溯联动
    //            data.remove(data.size() - 1);
    //            overIndexs.remove(i);
    //        }
    //    }
    //}






